Suppose I have user table my_users in which there is a primary key id. Also, I wish to design (in MySQL) a simple blacklist table, whose declaration looks like this:
CREATE TABLE IF NOT EXISTS black_list (
user_id INT NOT NULL,
bad_string VARCHAR(100) NOT NULL,
FOREIGN KEY (user_id) REFERENCES my_users(id),
PRIMARY KEY (user_id, bad_string));
The interpretation of any row in the black_list is that a user with the ID user_id wants to blacklist the string bad_string. Obviously, user_id cannot be unique since a single user may have more than one blacklisted string. Other way around, bad_string cannot be unique since more than one users may have blacklisted the same string. However, the pair (user_id, bad_string) should be unique since it makes no sense for the user to black list the same string more than once.
When we select a black list via a user ID (SELECT * FROM black_list WHERE user_id = X) in the worst case, MySQL will have to scan the entire black_list table.
My question here is: is there a way for running the above SELECT statement in sublinear time with regard to the number of rows in the black_list table? If yes, how can I accomplish that?